package main

func main() {

}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	tail := head
	// k 个一组，不足K个则返回头结点
	for i := 0; i < k; i++ {
		if tail == nil {
			return head
		}
		tail = tail.Next
	}

	// 继续找k个一组，已经分好组了
	next := reverseKGroup(tail, k)

	// 初始状态，pre指向后面已经分好的头结点， tail 指向当前头结点
	pre, tail := next, head
	// k个一组循环
	// 列如： 123  654
	// pre指向6，tail指向1
	for i := 0; i < k; i++ {
		// next2 指向tail的下一个，用于临时标记，待会tail会指向这个地方
		// next2 指向2，待会tail会调整到2，开始下一轮循环
		next2 := tail.Next
		// tail的下一个指向pre 1的下一个本来是2，现在指向6
		tail.Next = pre
		// pre 调整到 tail的位置
		// pre本来是6，现在调整到1
		pre = tail
		// tail调整到2
		tail = next2
		// 这一轮结束后，是 2 → 3 → 4   1→6→5→4
	}
	// 结束后，是 4→3→2→1→6→5→4
	return pre
}
